package wtx.geeks;

import java.util.StringJoiner;

/**
 * https://practice.geeksforgeeks.org/problems/-rearrange-array-alternately/0/
 * 很难给出时间O(n)，空间O(1)的解法
 */
public final class AlterArray {
    
  private void swap(int[] array, int i, int j) {
      int tmp = array[j];
      array[j] = array[i];
      array[i] = tmp;
  }
  public int[] alterSortArray(int[] array) {
    if (array == null || array.length < 2) {
      return array;
    }
    final int N = array.length;
    if (array.length < 4) {
      swap(array, 0, N-1);
      return array;
    }
    // int i = 0; 
    // int j = N - 1;
    // int stepi = 2;
    // for (;i < j;) {
    //   swap(array, i, j);
    //   i += stepi;
    //   --j; 
    // }
    // final int boundary = j+1;
    int a = 2;
    final int boundary = (int) (Math.log(N)/Math.log(2))+2;
    for (int e = 1; e < boundary; ++e) {
      int b = a/2 - 1;
      int k = 0;
      int i = a * k + b;
      for (int j = N-1; i < j; --j) {
        swap(array, i, j); 
        ++k;
        i = a * k + b;
      }
      a *= 2;
    }
    // if (N % 2 == 1) {
    //   int i = (a / 2 - 1) % N;
    //   swap(array, i, N - 1);
    // }
    return array;
  }

    /**
     * Says hello to the world.
     * @param args The arguments of the program.
     */
    public static void main(String[] args) {
      AlterArray aa = new AlterArray();
      for (int i = 9; i < 50; ++i) {
        int[] ary = new int[i];
        for (int j = 1; j <= i; ++j) {
          ary[j-1] = j;
        }
        aa.alterSortArray(ary);
        StringJoiner sj = new StringJoiner(", ", "[", "]");
        for (int j = 0; j < i; ++j) {
          sj.add("" + ary[j]);
        }  
        System.out.println(sj.toString());
      }
    }
}
